public class 在排序数组中查找元素的第一个和最后一个位置 {
    //https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
    //两次二分, 加判断
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        //0直接返回
        if(n == 0){
            return new int[]{-1,-1};
        }
        //左边界查找
        int l = 0;
        int r = n - 1;
        int ans1 = 0;
        while(l <= r){
            int m = (l + r) >> 1;
            if(nums[m] >= target){
                ans1 = m;
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        l = ans1;
        r = n - 1;
        int ans2 = 0;
        //右边界查找
        while(l <= r){
            int m = (l + r) >> 1;
            if(nums[m] <= target){
                ans2 = m;
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        //开始为空,必然为空
        if(nums[ans1] != target){
            return new int[]{-1,-1};
        }
        //右边界为空改成-1
        if(nums[ans2] != target){
            return new int[]{ans1,-1};
        }
        //否则直接返回
        return new int[]{ans1,ans2};
    }
}
